package LeetCode;

import java.util.HashMap;

/**
 * @Author：DijaH
 * @Date：2023/1/7 6:57 下午
 * @Version：1.0.0
 * @Description：
 * 滑动窗口
 */
public class code76_minWindow {

    public static String minWindow(String source, String target) {
        //使用滑动窗口的方式
        //字符串转换char
        char[] s = source.toCharArray();
        char[] t = target.toCharArray();
        //定义map，
        HashMap<Character,Integer> needs = new HashMap<>();
        HashMap<Character,Integer> window = new HashMap<>();
        int start = 0;
        int length = Integer.MAX_VALUE;
        int valid = 0;
        //将target中的值放到map中
        for(char c : t){
            needs.put(c,needs.getOrDefault(c,0) + 1);
        }
        int left = 0;
        int right = 0;
        while(right < s.length){
            //滑动右侧额窗口,扩大window
            char c = s[right];
            right++;
            //如果当前的位置存在于needs中，那么window中的map更新
            if(needs.containsKey(c)){
                window.put(c,window.getOrDefault(c,0) + 1);
                //如果当前窗口的位置的值 == needs中的c的 值 =》valid++
                if(window.get(c).equals(needs.get(c))){
                    valid++;
                }
            }
            while(valid == needs.size()){
                //如果 valid 等于了needs中的字符类型个数缩小窗口
                //缩小窗口，更新 start 和 length
                if(right - left < length){
                    start = left;
                    length = right - left;
                }
                //拿出将要缩小的左侧的位置的字符
                char d = s[left];
                left++;
                //判断当前d位置的字符是否在needs中
                if(needs.containsKey(d)){
                    //如果存在 needs中，将window中的value-1
                    window.put(d,window.get(d) - 1);
                    //如果wind中的 d 位置的value值 < needs中d位置的value值 ，那么 valid--
                    if(window.get(d) < Integer.valueOf(needs.get(d))){
                        valid--;
                    }
                }
            }
        }
        return length == Integer.MAX_VALUE ? "" : source.substring(start,start + length);
    }

    public static void main(String[] args) {
        String source = "EBBANCF";
        String target = "ABC";
        String s = minWindow(source, target);
        System.out.println(s);
    }
}
